package com.pandy.code;


/**
 * 归并排序
 * 时间复杂度 O(N*logN)
 *
 * 归并排序理解
 */
public class Code07_MergeSort {

    /**
     * 归并排序
     * @param arr
     */
    public static void mergeSort(int[] arr) {
        if(arr == null || arr.length < 2) {
            return;
        }

        process(arr, 0, arr.length-1);
    }

    /**
     * 递归完成左右排好序
     * @param arr
     * @param l
     * @param r
     */
    private static void process(int[] arr, int l, int r) {
        if(l >= r) {
            return;
        }

        int mid = l + ((r - l) >> 1);
        process(arr,l,mid);
        process(arr,mid+1,r);
        merge(arr,l,mid,r);
    }

    /**
     * 执行 merge方法 左右两边肯定是排好序的
     * @param arr
     * @param l
     * @param mid
     * @param r
     */
    public static void merge(int[] arr, int l, int mid, int r) {
        int[] help = new int[r-l+1];

        int i=0;

        //定义左右两个指针
        int h1 = l;
        int h2 = mid+1;

        // 两边比较近，谁小往help数组中的拷贝，指针后移
        while (h1 <= mid && h2 <= r) {
            help[i++] = arr[h1] <= arr[h2] ? arr[h1++] : arr[h2++];
        }

        // 以下两个while只会执行一个
        while (h1 <= mid) {
            help[i++] = arr[h1++];
        }

        while (h2 <= r) {
            help[i++] = arr[h2++];
        }

        // 拷贝
        for(int j=0; j<help.length; j++) {
            arr[l+j] = help[j];
        }
    }

    public static void print(int[] arr) {
        for(int i=0; i<arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {4,6,1,4,6,8,3,5,2,1,6};
        print(arr);
        mergeSort(arr);
        print(arr);
    }
}
